package com.li.algorithm.leetcode.hot100;

public class Test21 {
    /**
     * 方法1:二分查找
     *   时间复杂度：O(mlogn)
     *   空间复杂度：O(1)
     */
//    public boolean searchMatrix(int[][] matrix, int target) {
//        //每一行的最左和最右值判断该行是否可能包含target
//        for (int i = 0; i < matrix.length; i++) {
//            if (matrix[i][0] == target || matrix[i][matrix[i].length-1] == target) {
//                return true;
//            }
//            if (matrix[i][0] < target && matrix[i][matrix[i].length - 1] > target) {
//                //行内使用二分查找
//                int left = 0, right = matrix[i].length - 1;
//                while (left <= right) {
//                    int middle = (left + right) / 2;
//                    if (matrix[i][middle] == target) {
//                        return true;
//                    } else if (matrix[i][middle] > target) {
//                        right = middle - 1;
//                    } else {
//                        left = middle + 1;
//                    }
//                }
//            }
//        }
//        return false;
//    }

    /**
     * 方法二：z字型查找
     *
     * 以 matrix 中的 左下角元素 为标志数 flag ，则有:
     * 若 flag > target ，则 target 一定在 flag 所在 行的上方 ，即 flag 所在行可被消去。
     * 若 flag < target ，则 target 一定在 flag 所在 列的右方 ，即 flag 所在列可被消去。
     *
     * 时间复杂度 O(M+N)
     * 空间复杂度 O(1)
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (target > matrix[i][j]) {
                j++;
            } else if (target < matrix[i][j]) {
                i--;
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {1,4,7,11,15},
                {2,5,8,12,19},
                {3,6,9,16,22},
                {10,13,14,17,24},
                {18,21,23,26,30}
        };
        int[][] matrix1 = new int[][]{
                {-1, 3}
        };
        Test21 test21 = new Test21();
        System.out.println(test21.searchMatrix(matrix, 5));


    }
}
